package Leetcode.动态规划;

/**
 * @ClassName 把数字翻译成字符串
 * @since: 2023/7/22 11:46
 * @auth: kirito
 * @description:
 * 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，
 * 11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: 12258
 * 输出: 5
 * 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
 *
 * 变相的斐波那契数列 跳台阶问题
 **/
public class 把数字翻译成字符串 {
//    https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solutions/199945/mian-shi-ti-46-ba-shu-zi-fan-yi-cheng-zi-fu-chua-6/
    //    整个数字的翻译结果数=除去最后1位的部分的翻译结果、1
    public static int translateNum3(int num) {
        char[] ch = String.valueOf(num).toCharArray();
        int len = ch.length;
        int[] dp = new int[len + 1];
        dp[0] = 1;
        dp[1] = 1;
//        初始状态： dp[0]=dp[1]=1dp[0] = dp[1] = 1dp[0]=dp[1]=1 ，
//        即 “无数字” 和 “第 111 位数字” 的翻译方法数量均为 111 ；
//
//        返回值： dp[n]dp[n]dp[n] ，即此数字的翻译方案数量。
//
//        Q： 无数字情况 dp[0]=1dp[0] = 1dp[0]=1 从何而来？
//        A： 当 numnumnum 第 1,21, 21,2 位的组成的数字 ∈[10,25]\in [10,25]∈[10,25] 时，
//        显然应有 222 种翻译方法，即 dp[2]=dp[1]+dp[0]=2dp[2] = dp[1] + dp[0] = 2dp[2]=dp[1]+dp[0]=2 ，
//        而显然 dp[1]=1dp[1] = 1dp[1]=1 ，因此推出 dp[0]=1dp[0] = 1dp[0]=1 。

        for(int i = 2; i <= len; i++){
            int n = (ch[i - 2] - '0') * 10 + (ch[i - 1] - '0');
            if(n >= 10 && n <= 25){
                dp[i] = dp[i - 1] + dp[i - 2];
            }else{
                dp[i] = dp[i - 1];
            }
        }
        return dp[len];
    }

    public static int translateNum2(int num) {
        int a = 1, b = 1, x, y = num % 10;
        while(num > 9) {
            num /= 10;
            x = num % 10;
            int tmp = 10 * x + y;
            int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
            b = a;
            a = c;
            y = x;
        }
        return a;
    }



    //    public static int translateNum1(int num) {
//        if (num == 1){
//            return 1;
//        }
//        if (num == 2){
//            return 2;
//        }
//        return translateNum1(num-1) + translateNum1(num-2);
//    }
    public static int len(int num) {
        return Integer.toString(num).length();
    }
    public static void main(String[] args) {
        int num = 18822;
//        int len = len(num)-1;
//        System.out.println(translateNum1(len));
        System.out.println(translateNum3(num));
    }
}
